package leetcode.top100;



import utils.TreeNode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，
 * <p>
 * 使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
 * <p>
 * 例如：
 * <p>
 * 输入: 二叉搜索树:
 * 5
 * /   \
 * 2     13
 * <p>
 * 输出: 转换为累加树:
 * 18
 * /   \
 * 20     13
 * <p>
 * <p>
 * 解析：BST中序遍历 左-> 中 -> 右 是从小到大，我们只要反中序就能保证严格的从大到小。
 * <p>
 * 每次遍历过程中，只要把当前节点的值 + 上一个节点的值即可，这个过程是累加的 。
 * <p>
 * 拓展：如果这颗数是普通的二叉树，请完成。
 *
 * @since 2019/12/22 0022 下午 1:48
 */
public class Code538_ConvertBST_把BST转为累加树 {


    private int pre = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root == null) return root;
        TreeNode temp = root;
        inOrderReverse2(root);
        return temp;
    }


    /**
     * 方式2：反 中序遍历的迭代版
     */
    private TreeNode inOrderReverse2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = root;
        int pre = 0;
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                // 中序遍历是处理左孩子的
                root = root.right;
            } else {
                root = stack.pop();
                //中序遍历处理
                root.val += pre;
                pre = root.val;
                // 中序遍历中是处理右孩子的
                root = root.left;
            }
        }
        return temp;
    }

    /**
     * 方式1：反 中序遍历，递归版
     **/
    private void inOrderReverse(TreeNode root) {

        if (root == null) return;
        inOrderReverse(root.right);
        root.val += pre;
        pre = root.val;
        inOrderReverse(root.left);
    }

    /**
     * 拓展：对树进行遍历，遍历的过程中对每个节点再次进行遍历对比。
     * 这个过程中不能更新节点的值，否则别的节点对比的时候会错乱掉。
     *
     * 所以可以利用一个Map,存储节点和节点的最终值，都遍历完毕后更新节点的值
     */
    private static Map<TreeNode,Integer> map = new HashMap<>();
    public TreeNode convertBST2(TreeNode root) {
        if(root == null) return root;
        TreeNode temp = root;
        //要保持一个递归的节点和一个根节点。因为第二次处理中用到根节点
        process(root,temp);
        //更新所有的值
        map.forEach((K,V) -> {
            K.val = V;
        });
        return root;
    }
    /**
     * 适用于所有的二叉树先序遍历每个节点，对每个节点处理
     */
    private static void process(TreeNode root,TreeNode curNode){
        if(curNode == null) return;
        //在这里对每个节点 和 其他所有节点比较，再次先序遍历。
        //要定义临时变量指向根节点，传入处理函数，每次都是从根节点处理。
        //因为最后要返回根节点，所以不能改变root的引用。
        map.put(curNode,curNode.val);
        TreeNode tempRoot = root;
        preOrder(tempRoot,curNode);
        process(root,curNode.left);
        process(root,curNode.right);
    }
    private static void preOrder(TreeNode curNode,TreeNode targetNode){
        if(curNode == null) return;
        //这里不能够立即更新targetNode的值，不然会错乱。
        if(targetNode.val < curNode.val){
            map.put(targetNode,map.get(targetNode) + curNode.val);
        }
        preOrder(curNode.left,targetNode);
        preOrder(curNode.right,targetNode);
    }

}
